/****************************************
*   双向链表逻辑实现
 *  Created by zephyrus on 2024/6/23.
*****************************************/
#include "DLinkedList.h"

/**
 * 初始化
 * @param list
 */
void InitDList(DList *list)
{
    //申请头结点
    DNode *s = DNODE;
    assert(s != NULL);
    //初始化时管理结点头指针和尾指针都指向头结点
    list->first = list->last = s;
    //头结点的前驱指针域和后继指针域都先赋值为空
    list->last->next = NULL;
    list->last->prio = NULL;
    //此时还没有有效结点
    list->size = 0;
}

/**
 * 尾插入法
 * @param list
 * @param x
 */
void DLinkedList_push_back(DList *list, ElemType x)
{
    DNode *s = _buyDNode(x);
    s->prio = list->last;
    list->last->next = s;
    list->last = s;
    list->size++;
}

/**
 * 头插入法
 * @param list
 * @param x
 */
void DLinkedList_push_front(DList *list, ElemType x)
{
    //获取要插入的结点，为x创建一个结点
    DNode *s = _buyDNode(x);

    //如果这是第一个有效结点
    if (list->first == list->last)
    {
        list->last = s; //更改管理结点尾指针指向
    } else
    { //如果不是第一个有效结点
        //设置插入结点的后继指向
        s->next = list->first->next;
        //将插入结点设置为下一结点的前驱
        s->next->prio = s;
    }
    //设置插入结点的前驱
    s->prio = list->first;
    list->first->next = s;
    list->size++;
}

/**
 * 显示数据
 * @param list
 */
void DLinkedList_show_list(DList *list)
{
    DNode *p = list->first->next;
    while (p != NULL)
    {
        printf("%d-->", p->data);
        p = p->next;
    }
    printf("Nul. \n");
}

/**
 * 尾删除
 * @param list
 */
void DLinkedList_pop_back(DList *list)
{
    //如果没有有准备结点，无需删除
    if (list->size == 0)
        return;
    Node *p = list->first;
    while (p->next != list->last)
    {
        p = p->next;
    }

    free(list->last); //释放尾结点
    //重新指向
    list->last = p;
    list->last->next = NULL;
    list->size--;
}

/**
 * 头删除
 * @param list
 */
void DLinkedList_pop_front(DList *list)
{
    if (list->size == 0)
        return;
    //指向要删除的有效结点,第一个有效结点
    DNode *p = list->first->next;
    //如果这个结点是最后一个有效结点，需要更改管理结点尾指针指向
    if (list->first->next == list->last)
    {
        list->last = list->first;
        list->last->next = NULL;
    } else
    {
        //更改下一个结点的前驱指向
        p->next->prio = list->first;
        //更改头结点的后继指向
        list->first->next = p->next;
    }
    free(p);
    list->size--;
}

/**
 * 按值插入 当前双链表已经有序
 * @param list
 * @param x
 */
void DLinkedList_insert_val(DList *list, ElemType x)
{
    //查找插入结点的前一结点
    DNode *p = list->first;
    while (p->next != NULL && p->next->data < x)
    {
        p = p->next;
    }
    //如果这个结点是头结点
    if (p->next == NULL)
    {
        DLinkedList_push_back(list, x);
    } else
    {
        //获取插入结点
        DNode *s = _buyDNode(x);
        //设置插入结点的后继
        s->next = p->next;
        //将插入结点设备为下一个结点的前驱
        s->next->prio = s;
        //设置插入结点的前驱
        s->prio = p;
        //将插入结点设置为上一结点的后继
        p->next = s;
        list->size++;
    }
}

/**
 * 查找
 * @param list
 * @param x
 */
DNode *DLinkedList_find(DList *list, ElemType x)
{
    Node *p = list->first->next;
    while (p != NULL && p->data != x)
        p = p->next;
    return p;
}

/**
 * 求有效结点
 * @param list
 * @return
 */
int DLinkedList_length(DList *list)
{
    return list->size;
}

/**
 * 删除特定值的结点
 * @param list
 * @param x
 */
void DLinkedList_deleted_val(DList *list, ElemType x)
{
    if (list->size == 0)
        return;
    //查找要删除的结点
    DNode *p = DLinkedList_find(&list, x);
    if (p == NULL)
    { //没有找到退出
        printf("the data not found to be deleted . \n");
        return;
    }
    if (p == list->last)
    { //如果是尾节点，进行尾删除
        list->last = p->prio; //指向要删除的节点p的前驱节点，向前移动指针
        list->last->next = NULL; //并将前驱节点，指向next的指针设为NULL
    } else //普通位置的节点 直接删除
    {
        //将要删除的节点的上一节点设置为下一个节点前驱
        p->next->prio = p->prio;
        //将要删除结点的下一节点设置为该结点上一结点的后继
        p->prio->next = p->next;
    }
    free(p);
    list->size--;
}

/**
 * 排序（升序)
 * @param list
 */
void DLinkedList_sort(DList *list)
{
    if (list->size == 0 || list->size == 1)
        return;
    //断开双链表//拆分成两个双链表
    DNode *s = list->first->next; //指向前一个双链表(目前只有一个有效结点)
    DNode *q = s->next;//指向每2个有效节点（含有除第一个有效结点之外的其余有效结点）
    //此时双链表的管理结点管理第一条双链表，设置尾指针指向
    list->last = s;
    list->last->next = NULL;

    //当第2个双链表中包含有效节点 ，需要继续取出按顺序插入到每一个又链表中
    while (q != NULL)
    {
        //取出每二个双链表的有效节点
        s = q;
        q = q->next;

        DNode *p = list->first;  //定义指针
        while (p->next != NULL && p->next->data < s->data)
        {
            p = p->next;
        }
        if (p->next == NULL) //如果位置在尾部，尾插入
        {
            //设置插入结点的后继结点为空
            s->next = NULL;
            //设置插入结点的前驱结点为之前的尾结点
            s->prio = list->last;
            //设置插入结点为之前尾结点的后继结点
            list->last->next = s;
            //更新管理结点中尾结点指向
            list->last = s;

        } else
        {
            //设置插入结点的后继
            s->next = p->next;
            //将插入结点设置为其下一结点的前驱结点
            s->next->prio = s;
            //设置插入结点的前驱结点
            s->prio = p;
            //将插入结点设置为其上一结点的后继
            p->next = s;
        }
    }

}

/**
 * 链表倒置
 * @param list
 */
void DLinkedList_resver(DList *list)
{
    if (list->size == 0 || list->size == 1)
        return;
    //拆分
    DNode *p = list->first->next;
    DNode *q = p->next;
    list->last = p;
    list->last->next = NULL;
    while (q != NULL)
    {
        p = q;
        q = q->next;
        p->next = list->first->next;
        p->next->prio = p;
        p->prio = list->first;
        list->first->next = p;
    }

}

/**
 * 清除所有的有效结点
 * @param list
 */
void DLinkedList_clear(DList *list)
{
    if (list->size == 0)
    {
        return;
    }
    DNode *p = list->first->next;
    while (p != NULL)
    {
        if (p == list->last)
        {
            list->last = list->first;
            list->last->next = NULL;
        } else
        {
            p->next->prio = list->first;
            list->first->next = p->next;
        }
        free(p);
        p = list->first->next;
    }
    list->size = 0;
}

/**
 * 销毁双链表
 * @param list
 */
void DLinkedList_destory(DList *list)
{
    DLinkedList_clear(list);
    free(list->first);
    list->first = list->last = NULL;
}